We extend the Approximate-Proximal Point (aProx) family of model-based methods for solving stochastic convex optimization problems, including stochastic subgradient, proximal point, and bundle methods, to the minibatch setting. To do this, we propose two minibatched algorithms for which we prove a non-asymptotic upper bound on the rate of convergence, revealing a linear speedup in minibatch size. In contrast to standard stochastic gradient methods, these methods may have linear speedup in the minibatch setting even for non-smooth functions. Our algorithms maintain the desirable traits characteristic of the aProx family, such as robustness to initial step size choice. Additionally, we show improved convergence rates for interpolation problems, which (for example) gives a new parallelization strategy for alternating projections. We corroborate our theoretical results with extensive empirical testing, which demonstrates the gains provided by accurate modeling and minibatching.

Strengths: The paper picks a very relevant problem. While the stochastic gradient method is easily parallelizable, parallelization strategies for the otherwise beneficial in terms of convergence rates approximate proximal methods are not known yet. The paper proposes natural approaches to parallelize the proximal methods: to compute the updates by independent workers and perform the averaged update (PIA), to build a model for the averaged function and compute the update which can be decomposed as a sum of independently computed terms (PMA), or to build an average of the models and compute an update, which can be parallelized through solving a dual problem (PAM). The paper clearly explains these strategies. It proves upper bounds for the errors in case of smooth and non-smooth functions.

We extend the Approximate-Proximal Point (aProx) family of model-based methods for solving stochastic convex optimization problems, including stochastic subgradient, proximal point, and bundle methods, to the minibatch setting. To do this, we propose two minibatched algorithms for which we prove a non-asymptotic upper bound on the rate of convergence, revealing a linear speedup in minibatch size. In contrast to standard stochastic gradient methods, these methods may have linear speedup in the minibatch setting even for non-smooth functions. Our algorithms maintain the desirable traits characteristic of the aProx family, such as robustness to initial step size choice. Additionally, we show improved convergence rates for "interpolation" problems, which (for example) gives a new parallelization strategy for alternating projections.